package com.fw.leetcode.linkedlist;

import com.fw.leetcode.LeetCode;

/**
 * 92. Reverse Linked List II
 *
 * Given the head of a singly linked list and two integers left and right where left <= right,
 * reverse the nodes of the list from position left to position right, and return the reversed list.
 *
 * Example 1:
 *  Input: head = [1,2,3,4,5], left = 2, right = 4
 *  Output: [1,4,3,2,5]
 *
 * Example 2:
 *  Input: head = [5], left = 1, right = 1
 *  Output: [5]
 *
 * Constraints:
 *  The number of nodes in the list is n.
 *  1 <= n <= 500
 *  -500 <= Node.val <= 500
 *  1 <= left <= right <= n
 *
 * Follow up: Could you do it in one pass?
 */
public class Num_0092 implements LeetCode {
    private interface Solution extends LinkedList {
        ListNode reverseBetween(ListNode head, int left, int right);

        default void assertExpected(int[] head, int left, int right, int[] expected) {
            if (!assertEquals(reverseBetween(build(head), left, right), build(expected))) {
                reverseBetween(build(head), left, right);
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public ListNode reverseBetween(ListNode head, int left, int right) { // 最优：一次遍历：时O(n) 空O(1)
            /*
             * 反转链表区域 [left, right]，仅允许一次遍历，left|right 不是数组下表索引，从链表1开始
             *       [1,2,3,4,5,6], left=3, right=5
             *          ↑ ↑
             * 1:    [1,2,4,3,5,6]
             *          ↑   ↑
             * 2:    [1,2,5,4,3,6]
             *          ↑     ↑
             */
            ListNode header = new ListNode(-1, head); // 建立辅助头节点
            ListNode prev = header;
            ListNode cur = prev.next;
            int num = right - left; // 需要移动元素的个数
            while (--left > 0) { // 找起始位置
                prev = cur;
                cur = cur.next;
            }
            while (num-- > 0) { // prev 固定，cur 逐步后移，cur.next 元素逐个插入到 prev.next
                // 1.
                ListNode curNextNextTmp = cur.next.next;
                cur.next.next = prev.next;
                // 2.
                prev.next = cur.next;
                // 3.
                cur.next = curNextNextTmp;
            }
            return header.next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertExpected(new int[]{1,2,3,4,5}, 2, 4, new int[]{1,4,3,2,5});
        solution.assertExpected(new int[]{5}, 1, 1, new int[]{5});
    }
}
